package org.labuladong.前缀和技巧;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @Auther: qingle
 * @Date: 2024/10/26-12:00
 * @Description:
 *
 * 有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。
 *
 * 一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足  xstart ≤ x ≤ xend，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。
 *
 * 给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。
 *
 *
 * 示例 1：
 *
 * 输入：points = [[10,16],[2,8],[1,6],[7,12]]
 * 输出：2
 * 解释：气球可以用2支箭来爆破:
 * -在x = 6处射出箭，击破气球[2,8]和[1,6]。
 * -在x = 11处发射箭，击破气球[10,16]和[7,12]。
 *
 * @version: 1.0
 */
public class LC452_用最少数量的箭引爆气球 {

	public int findMinArrowShots(int[][] points) {
		int n = points.length;
		if(n == 0) return 0;

		// 根据区间的结束时间进行排序
		Arrays.sort(points, Comparator.comparingInt(a -> a[1]));

		/**
		 * //TODO 使用 Comparator.comparingInt 方法时，Java 内部会处理可能的整数溢出问题
		 * Comparator.comparingInt(a -> a[1]) 定义了排序的逻辑：根据每个区间的结束时间（a[1]）进行比较。
		 * 如果一个区间的结束时间小于另一个区间的结束时间，它会被排在前面。
		 * 如果两个区间的结束时间相同，它们的相对顺序会保持不变（因为 Comparator 是稳定的）。
		 * {{1, 2}, {2, 3}, {1, 4}, {3, 5}}
		 */

		int count = 1;// 初始化，至少有一个区间
		int end = points[0][1];// 初始化，第一个区间的结束时间
		for(int i = 1; i < n; i++) {
			// 如果当前区间的开始时间大于结束时间，则该区间可以加入

			// 这个条件确保了我们尽可能地合并可以被同一支箭覆盖的气球，并且只对那些不能被任何已射箭覆盖的气球射出新的箭。
			if(points[i][0] > end) {
				count++;
				// 更新结束时间为当前区间的结束时间
				end = points[i][1];
			}
		}
		return count;// 返回最多活动数

	}

	public static void main(String[] args) {

		int[][] points = {{10,16},{2,8},{1,6},{7,12}};
		LC452_用最少数量的箭引爆气球 solution = new LC452_用最少数量的箭引爆气球();
		int minArrowShots = solution.findMinArrowShots(points);
		System.out.println(minArrowShots);
	}
}
